#include <bits/stdc++.h>
// 2025/02/07
// tag:
// Author: Zhang Muen
using namespace std;
#define int long long
class State {
public:
    int id, weight;
    State(int i, int w)
    {
        id = i;
        weight = w;
    }
};

int n, m, s, dist[601], vis[601], w[601];
vector<State> graph[601];

void Dijkstra(int start)
{
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[start] = 0;
    for (int i = 0; i < n; i++) {
        int p = -1;
        for (int j = 0; j < n; j++)
            if (!vis[j] && (dist[j] < dist[p] || p == -1))
                p = j;
        vis[p] = true;
        memset(w, 0x3f, sizeof w);
        int m = 0x3f3f3f3f;
        for (auto x : graph[p])
            w[(x.id + dist[p]) % n] = x.weight;
        for (int i = 0; i < n; i++)
            m = min(m, w[i] - i), w[i] = min(w[i], m + i);
        m = 0x3f3f3f3f;
        for (int i = n - 1; i >= 0; i--)
            m = min(m, w[i] - i), w[i] = min(w[i], m + n + i);
        for (int i = 0; i < n; i++)
            dist[i] = min(dist[i], w[i] + dist[p]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    cin >> n >> m;
    int u, v, w;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        graph[u].push_back(State(v, w));
    }
    for (int i = 0; i < n; i++) {
        Dijkstra(i);
        for (int j = 0; j < n; j++)
            cout << dist[j] << " ";
        cout << endl;
    }
    return 0;
}
